package com.cwj.algorithm.graph;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author chenwujie
 * @date 2020-12-23 15:45
 * 深度优先排序
 */
public class DepthFirstOrder {
    private Digraph digraph;
    private boolean[] marked;
    private Deque<Integer> sequence;

    public DepthFirstOrder(Digraph digraph){
        this.digraph = digraph;
        marked = new boolean[digraph.getV()];
        sequence = new LinkedList<>();
    }

    /**
     * 对有向图顶点排序
     * @return 返回一个结果栈，栈顶元素是第一个元素
     */
    public Deque<Integer> order(){
        for (int i = 0; i < digraph.getV(); i++) {
            if(!marked[i]){
                dfs(i);
            }

        }
        return sequence;
    }

    private void dfs(int v){
        marked[v] = true;
        for (Integer w : digraph.getVertexes(v)) {
            if(!marked[w]){
                dfs(w);
            }
        }
        sequence.push(v);
    }
}
